package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/possible-bipartition/
 * @create 2025/10/11 21:12
 * @since JDK17
 */

public class Solution45 {
    boolean ok = true;
    boolean[] vis, color;
    List<Integer>[] g;
    void dfs(int cur) {
        if (!ok) {
            return;
        }
        vis[cur] = true;    // 标记已经被遍历了
        for (int next : g[cur]) {
            if (!vis[next]) {   // 没有便遍历过
                color[next] = !color[cur];  // 染色
                dfs(next);
            } else {    // 该节点已经被遍历过，检查上一个节点是否被遍历过
                if (color[next] == color[cur]) {    // 染色失败
                    ok = false;
                }
            }
        }

    }
    public boolean possibleBipartition(int n, int[][] dislikes) {
        n++;
        vis = new boolean[n];
        color = new boolean[n];
        g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (var x : dislikes) {
            g[x[0]].add(x[1]);
            g[x[1]].add(x[0]);
        }
        for (int i = 1; i < n; i++) {
            dfs(i);
        }
        return ok;
    }
}
